Grafo de Kneser

Grafo de Kneser
El grafo de Kneser K(5, 2), isomorfo al grafo de Petersen
Nombre en honor a	Martin Kneser
Vértices	${\binom {n}{k}}$
Aristas	${\frac {1}{2}}{\binom {n}{k}}{\binom {n-k}{k}}$
Número cromático	${\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}$
Propiedades	${\tbinom {n-k}{k}}$-regular arco-transitivo
Notación	K(n, k), KGn,k.

En teoría de grafos, el grafo de Kneser K(n, k) (alternativamente KG_n,k) es el grafo cuyos vértices corresponden a los subconjuntos de k elementos de un conjunto de n elementos, y donde dos vértices son adyacentes si y solo si los dos correspondientes conjuntos son disjuntos. Los grafos de Kneser llevan el nombre de Martin Kneser, quien los investigó por primera vez en 1956.

Ejemplos

Grafo de Kneser O₄= K(7, 3)

El grafo de Kneser K(n, 1) es el grafo completo de n vértices.

El grafo de Kneser K(n, 2) es el complemento del grafo línea del grafo completo sobre n vértices.

El grafo de Kneser K(2n − 1, n − 1) es el grafo impar O_n; en particular, O₃= K(5, 2) es el grafo de Petersen (véase la figura de la parte superior derecha).

El grafo de Kneser O₄= K(7, 3), visualizado a la derecha.

Propiedades

Propiedades básicas

• El grafo de Kneser $K(n,k)$ tiene ${\tbinom {n}{k}}$ vértices. Cada vértice tiene exactamente ${\tbinom {n-k}{k}}$ vecinos.
• El grafo de Kneser es transitivo de vértices y arco transitivo.
• Cuando $k=2$, el grafo de Kneser es un grafo fuertemente regular, con parámetros $({\tbinom {n}{2}},{\tbinom {n-2}{2}},{\tbinom {n-4}{2}},{\tbinom {n-3}{2}})$. Sin embargo, no es muy regular cuando $k>2$, ya que diferentes pares de vértices no adyacentes tienen diferentes números de vecinos comunes según el tamaño de la intersección de los correspondientes pares de conjuntos.
• Debido a que los grafos de Kneser son regulares y transitivo de vínculos, su conectividad de vértices es igual a su grado, excepto por $K(2k,k)$ que está desconectado. Más precisamente, la conectividad de $K(n,k)$ es ${\tbinom {n-k}{k}},$ igual al número de vecinos por vértice (Watkins, 1970).

Número cromático

Como conjeturó txt,, el coloreado del grafo de Kneser K(n, k) para $n\geq 2k$ es exactamente n − 2k + 2. Por ejemplo, el grafo de Petersen requiere tres colores en cualquier coloración propia. Esta conjetura se ha demostrado de varias maneras.

• txt, demostró esto utilizando métodos topológicos, dando lugar al campo de la combinatoria topológica.
• Poco tiempo después,txt, dio una prueba simple, usando el teorema de Borsuk-Ulam y un lema de David Gale.
• txt, ganó el premio Morgan por una prueba aún más simplificada pero todavía topológica.
• txt, encontró una prueba combinatoria puramente.

Cuando $n<2k$, el número cromático de K(n, k) es 1.

Ciclo hamiltoniano

• El grafo de Kneser K(n, k) contiene un camino hamiltoniano si (Chen, 2003):

$n\geq {\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right).$

Ya que

${\frac {1}{2}}\left(3k+1+{\sqrt {5k^{2}-2k+1}}\right)<\left({\frac {3+{\sqrt {5}}}{2}}\right)k+1,$

válido para todo k. Esta condición se cumple si

$n\geq \left({\frac {3+{\sqrt {5}}}{2}}\right)k+1\approx 2.62k+1.$

• El grafo de Kneser K(n, k) contiene un ciclo hamiltoniano si existe un entero no negativo a tal que $n=2k+2^{a}$ (Mütze, Nummenpalo y Walczak, 2018). En particular, el grafo impar O_n tiene un ciclo hamiltoniano si n ≥ 4.
• Con la excepción del grafo de Petersen, todos los grafos de Kneser conectados K(n, k) con n ≤ 27 son hamiltonianos (Shields, 2004).

Cliques

• Cuando n < 3k, el grafo de Kneser K(n, k) no contiene triángulos. De manera más general, cuando n < ck no contiene cliques de tamaño c, mientras que contiene tales cliques cuando n ≥ ck. Además, aunque el grafo de Kneser siempre contiene ciclos de longitud cuatro siempre que n ≥ 2k + 2, para valores de n cercanos a 2k, el ciclo impar más corto puede tener una longitud variable (Denley, 1997).

Diámetro

• El diámetro de un grafo de Kneser conectado K(n, k) es (Valencia-Pabon y Vera, 2005):

$\left\lceil {\frac {k-1}{n-2k}}\right\rceil +1.$

Espectro

• El espectro del grafo de Kneser K(n, k) consta de k + 1 autovalores distintos:

$\lambda _{j}=(-1)^{j}{\binom {n-k-j}{k-j}},\qquad j=0,\ldots ,k.$

Además $\lambda _{j}$ aparece con multiplicidad ${\tbinom {n}{j}}-{\tbinom {n}{j-1}}$ para $j>0$ y $\lambda _{0}$ tiene multiplicidad 1.​

Número de independencia

• El teorema Erdős-Ko-Rado establece que el conjunto independiente del grafo de Kneser K(n, k) para $n\geq 2k$ es

$\alpha (K(n,k))={\binom {n-1}{k-1}}.$

Grafos relacionados

El grafo de Johnson J(n, k) es aquel cuyos vértices son los subconjuntos de k elementos de un conjunto de n elementos, siendo dos vértices adyacentes cuando se encuentran en un conjunto de (k − 1) elementos. El grafo de Johnson J(n, 2) es el complemento del grafo de Kneser K(n, 2). Los grafos de Johnson están estrechamente relacionados con el esquema de Johnson, que llevan el nombre de Selmer M. Johnson.

El grafo de Kneser generalizado K(n, k, s) tiene el mismo conjunto de vértices que el grafo de Kneser K(n, k), pero conecta dos vértices siempre que correspondan a conjuntos que se cruzan en s o menos elementos (Denley, 1997). Así K(n, k, 0)= K(n, k).

El grafo de Kneser bipartito H(n, k) tiene como vértices los conjuntos de k y de n − k elementos extraídos de una colección de n elementos. Dos vértices están conectados por una arista siempre que un conjunto es un subconjunto del otro. Al igual que el grafo de Kneser, es vértice transitivo con grado ${\tbinom {n-k}{k}}.$. El grafo de Kneser bipartito se puede formar como un recubrimiento doble bipartito de K(n, k) en el que se hacen dos copias de cada vértice y se reemplaza cada vínculo por un par de vínculos que conectan los correspondientes pares de vértices (Simpson, 1991). El grafo de Kneser bipartito H(5, 2) es el grafo de Desargues y el grafo de Kneser bipartito H(n, 1) es un grafo en corona.

Bibliografía

• Bárány, Imre (1978), «A short proof of Kneser's conjecture», Journal of Combinatorial Theory, Series A 25 (3): 325-326, MR 0514626, doi:10.1016/0097-3165(78)90023-7 .
• Chen, Ya-Chen (2003), «Triangle-free Hamiltonian Kneser graphs», Journal of Combinatorial Theory, Series B 89 (1): 1-16, MR 1999733, doi:10.1016/S0095-8956(03)00040-6 .
• Denley, Tristan (1997), «The odd girth of the generalised Kneser graph», European Journal of Combinatorics 18 (6): 607-611, MR 1468332, doi:10.1006/eujc.1996.0122 .
• Greene, Joshua E. (2002), «A new short proof of Kneser's conjecture», American Mathematical Monthly 109 (10): 918-920, JSTOR 3072460, MR 1941810, doi:10.2307/3072460 .
• Kneser, Martin (1956), «Aufgabe 360», Deutsche Mathematiker-Vereinigung 58 (2): 27 .
• Lovász, László (1978), «Kneser's conjecture, chromatic number, and homotopy», Journal of Combinatorial Theory, Series A 25 (3): 319-324, MR 0514625, doi:10.1016/0097-3165(78)90022-5, hdl:10338.dmlcz/126050 .
• Matoušek, Jiří (2004), «A combinatorial proof of Kneser's conjecture», Combinatorica 24 (1): 163-170, MR 2057690, doi:10.1007/s00493-004-0011-1, hdl:20.500.11850/50671 .
• Mütze, Torsten; Nummenpalo, Jerri; Walczak, Bartosz (2018), «Sparse Kneser graphs are Hamiltonian», STOC'18—Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, New York: ACM, pp. 912-919, MR 3826304, arXiv:1711.01636 .
• Shields, Ian Beaumont (2004), Hamilton Cycle Heuristics in Hard Graphs, Ph.D. thesis, Universidad Estatal de Carolina del Norte, archivado desde el original el 17 de septiembre de 2006, consultado el 1 de octubre de 2006 .
• Simpson, J. E. (1991), «Hamiltonian bipartite graphs», Proceedings of the Twenty-Second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), Congressus Numerantium 85, pp. 97-110, MR 1152123 .
• Valencia-Pabon, Mario; Vera, Juan-Carlos (2005), «On the diameter of Kneser graphs», Discrete Mathematics 305 (1–3): 383-385, MR 2186709, doi:10.1016/j.disc.2005.10.001 .
• Watkins, Mark E. (1970), «Connectivity of transitive graphs», Journal of Combinatorial Theory 8: 23-29, MR 266804, doi:10.1016/S0021-9800(70)80005-9 .

Enlaces externos

• Weisstein, Eric W. «Kneser Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Odd Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q733004